/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						       clip_list.h

	$Header: /game/clip_list.h $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "clip_list.h"

t_rect_list_cache_ptr	get_global_free_rect_list()
{
	static t_rect_list_cache_ptr global_free_list = new t_rect_list_cache;
	return global_free_list;
}

////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////

t_rect_list_cache::t_rect_list_cache() : m_rects_free(k_global_freelist_const::k_global_pre_alloc_limit)
{}

t_rect_list_cache::~t_rect_list_cache()
{
	m_rects_free.clear();
}

////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////

inline bool rect_overlap( t_screen_rect const & rect_a, t_screen_rect const & rect_b )
{
	//test overlap function
	return		rect_a.left <= rect_b.right
			&&	rect_b.left <= rect_a.right
			&&	rect_a.top  <= rect_b.bottom
			&&	rect_b.top  <= rect_a.bottom;
}

inline bool rect_contains( t_screen_rect const & outer, t_screen_rect const & inner )
{
	if (!(	outer.left < inner.right
		&&	inner.left < outer.right
		&&	outer.top  < inner.bottom
		&&	inner.top  < outer.bottom ))
		return false;
	
	return outer.left <= inner.left && outer.right >= inner.right && outer.top <= inner.top && outer.bottom >= inner.bottom;
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 t_clip_list::t_clip_list() : m_extent(0,0,0,0)
{
	 m_global_free_rect_list = get_global_free_rect_list();
}
 
 t_clip_list::t_clip_list( t_screen_rect const& rect )
{
	m_global_free_rect_list = get_global_free_rect_list();

	m_global_free_rect_list->push_back_use_free_list ( m_rects, rect );

	m_extent = rect;
}

 t_clip_list::t_clip_list(const t_clip_list& clist)
{
	m_global_free_rect_list = get_global_free_rect_list();

	clear();
	
	m_extent = clist.m_extent;
	
	std::list<t_screen_rect>::const_iterator iter;
	
	for (iter = clist.m_rects.begin(); iter != clist.m_rects.end(); iter++)
	{
		m_global_free_rect_list->push_back_use_free_list(m_rects, *iter);
	}
}

 t_clip_list& t_clip_list::operator=(const t_clip_list& clist)
{
	 m_global_free_rect_list = get_global_free_rect_list();

	if (&clist != this)
	{
		clear();

		m_extent = clist.m_extent;
		
		std::list<t_screen_rect>::const_iterator iter;
		
		for (iter = clist.m_rects.begin(); iter != clist.m_rects.end(); iter++)
		{
			m_global_free_rect_list->push_back_use_free_list(m_rects, *iter);
		}
	}

	return *this;
}
 
t_clip_list::~t_clip_list()
{
	clear();
	m_global_free_rect_list = NULL;
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 void t_clip_list::clear()
{
	m_extent = t_screen_rect(0,0,0,0);	
	m_global_free_rect_list->clear_rect_list(m_rects);
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 bool t_clip_list::contains( t_screen_rect const& rect ) const
{
	 if (!rect_contains(m_extent, rect))
		 return false;
	
	t_clip_list regions( rect );

	regions -= *this;
	return regions.empty();
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 bool t_clip_list::intersects( t_screen_rect const& rect ) const
{
	if (!rect_overlap( m_extent, rect ))
		return false;

	t_const_iterator index = m_rects.begin();

	while (index != m_rects.end())
	{
		if (rect_overlap( *index, rect ))
			return true;
		index++;
	}
	return false;
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 void t_clip_list::offset( t_screen_point const& point )
{
	t_iterator index;

	for (index = m_rects.begin(); index != m_rects.end(); index++)
		*index += point;
	m_extent += point;
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 void t_clip_list::update_extent()
{
	if (m_rects.empty())
	{
		m_extent = t_screen_rect(0,0,0,0);
		return;
	}

	t_iterator index = m_rects.begin();

	m_extent = *index++;
	while (index != m_rects.end())
	{
		m_extent = ::get_extent( m_extent, *index++ );
	}
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 bool t_clip_list::remove( t_screen_rect const& rect )
{
	if (!rect_overlap( rect, m_extent ))
		return false;

	if (rect_contains(rect, m_extent))
	{
		m_global_free_rect_list->clear_rect_list(m_rects);
		return true;
	}

	t_iterator    index = m_rects.begin();
	t_iterator    last;
	t_iterator    next;
	t_screen_rect old_rect;
	t_screen_rect center;
	t_screen_rect new_rect;
	bool          changed = false;

	while (index != m_rects.end())
	{
		// find the intersection of the new rectangle and the one on the list

		if (rect_overlap(rect, *index) == false)
		{
			index++;
		}
		else
		{
			center = intersection( rect, *index );
		
			if (center.height() <= 0 || center.width() <= 0)
			{
				index ++;
				continue;
			}

			changed = true;
			last = index;
			old_rect = *index++;   // make a copy of the old rectangle and remove it
			
			m_global_free_rect_list->add_to_free_list( m_rects, last );
			
			// determine what remains of the rectangle after we remove the new one.
			new_rect = old_rect;
			new_rect.bottom = center.top;
			if (new_rect.height() > 0)
				m_global_free_rect_list->push_front_use_free_list ( m_rects, new_rect );
			
			new_rect.top = center.top;
			new_rect.bottom = center.bottom;
			new_rect.right = center.left;
			
			if (new_rect.width() > 0)
				m_global_free_rect_list->push_front_use_free_list ( m_rects, new_rect );
			
			new_rect.left = center.right;
			new_rect.right = old_rect.right;

			if (new_rect.width() > 0)
				m_global_free_rect_list->push_front_use_free_list ( m_rects, new_rect );

			new_rect = old_rect;   
			new_rect.top = center.bottom;

			if (new_rect.height() > 0) 
				m_global_free_rect_list->push_front_use_free_list ( m_rects, new_rect );
		}
	}
	return changed;
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 t_clip_list& t_clip_list::operator-=( t_screen_rect const& rect )
{
	if (remove( rect ))
		update_extent();
	return *this;
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 bool t_clip_list::remove( t_clip_list const& regions )
{
	if ( !rect_overlap( m_extent, regions.get_extent() ) )
		return false;

	t_const_iterator index;
	bool             changed = false;

	for (index = regions.begin(); index != regions.end(); index++)
	{
		if (remove( *index ))
		{
			changed = true;
			if (m_rects.empty())
				return true;
		}
	}
	return changed;
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 t_clip_list& t_clip_list::operator -= ( t_clip_list const& regions )
{
	if ( remove( regions ))
	{
		merge_rectangles();
		update_extent();
	}
	return *this;
}


// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 bool t_clip_list::operator == (t_clip_list const& regions) const
{
	if (m_extent != regions.m_extent)
		return false;

	t_clip_list result = regions;

	result.remove( *this );
	if (!result.empty())
		return false;

	result = *this;
	result.remove( regions );
	return result.empty();
}


// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
// check first rectangle in list to see if it can be merged with any
// later ones
 void t_clip_list::merge_rectangles()
{
	if (m_rects.empty() || m_rects.front() == m_extent)
		return;

	t_iterator    index;
	t_screen_rect rect;

	while (true)
	{
		// find a rectangle which shares an edge with the current rectangle.
		index = m_rects.begin();
		rect = *index++;

		while (index != m_rects.end())
		{
			// is it directly above or below?
			if (rect.left == index->left && rect.right == index->right)
			{
				if (rect.bottom == index->top)
				{
					begin()->bottom = index->bottom;
					break;
				}
				if (rect.top == index->bottom)
				{
					begin()->top = index->top;
					break;
				}
			}
			// is it directly left or right?
			if (rect.top == index->top && rect.bottom == index->bottom)
			{
				if (rect.right == index->left)
				{
					begin()->right = index->right;
					break;
				}
				if (rect.left == index->right)
				{
					begin()->left = index->left;
					break;
				}
			}
			index++;
		}

		// if we found and merged a rectangle, delete it.  Else stop.
		if (index != m_rects.end())
		{
			m_global_free_rect_list->add_to_free_list( m_rects, index );
		}
		else
			break;
	}
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 t_clip_list& t_clip_list::operator+=( t_screen_rect const& rect )
{
	if (m_rects.empty())
	{
		m_extent = rect;
		m_global_free_rect_list->clear_rect_list(m_rects);
	}
	else
	{
		if (contains( rect ))
			return *this;
		remove( rect );
		m_extent = ::get_extent( m_extent, rect );
	}

	m_global_free_rect_list->push_front_use_free_list ( m_rects, rect );
	merge_rectangles();
	return *this;
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 t_clip_list& t_clip_list::operator += ( t_clip_list const& regions )
{
	if (regions.empty())
		return *this;

	if (m_rects.empty())
	{
		*this = regions;
		return *this;
	}
	if (m_rects.front() == m_extent && ::contains( m_extent, regions ))
		return *this;
	if (regions.m_rects.front() == regions.m_extent)
		return (*this += *regions.begin());

	remove( regions ); 

	t_const_iterator index;

	for (index = regions.begin(); index != regions.end(); index++)
		m_global_free_rect_list->push_front_use_free_list ( m_rects, *index );

	m_extent = ::get_extent( m_extent, regions.get_extent() );    
	merge_rectangles();
	return *this;
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
// remove all areas not within "rect"
 void t_clip_list::intersect( t_screen_rect const& rect )
{
	// if the clip list is entirely within rect, stop.

	 if (rect_contains(rect, m_extent))
		 return;

	if (!rect_overlap( m_extent, rect ) )
	{
		clear();
		return;
	}

	t_iterator    index = m_rects.begin();
	t_iterator    last;

	while (index != m_rects.end())
	{
		if (rect_overlap( rect, *index ) == false)
		{
			last = index++;   
			m_global_free_rect_list->add_to_free_list( m_rects, last );
		}
		else
		{
			*index = ::intersection( rect, *index );
			if (index->width() <= 0 || index->height() <= 0)
			{
				last = index++;   
				m_global_free_rect_list->add_to_free_list( m_rects, last );
			}
			else
				index++; 
		}
	}
	update_extent();
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
 void t_clip_list::intersect( t_clip_list const& regions )
{
	if (m_rects.empty())
		return;

	if (regions.empty() || !rect_overlap( m_extent, regions.get_extent() ))
	{
		clear();
		return;
	}

	if (m_rects.front() == m_extent && ::contains( m_extent, regions ))
	{
		*this = regions;
		return;
	}

	if (regions.m_rects.front() == regions.m_extent)
	{
		intersect( *regions.begin() );
		return;
	}

	std::list<t_screen_rect> result_rects;

	t_iterator       index;
	t_const_iterator source;
	t_screen_rect    result;
	t_screen_rect    rect;

	for (source = regions.begin(); source != regions.end(); source++)
	{
		rect = *source;
		for (index = m_rects.begin(); index != m_rects.end(); index++)
		{
			if (rect_overlap( rect, *index ) == true)
			{
				result = intersection( rect, *index );
				
				if (result.width() > 0 && result.height() > 0)
				{
					m_global_free_rect_list->push_back_use_free_list(result_rects,result);
				}
			}
		}
	}
	m_rects = result_rects;
	merge_rectangles();
	update_extent();
 }

// ---------------------------------------------------------------
// Compute the intersection of a clip list and a rectangle
// ---------------------------------------------------------------
 t_clip_list intersection( t_clip_list const & first, t_screen_rect const & second )
{
	 if (rect_contains(second, first.m_extent))
		 return first;

	t_clip_list result;

	if ( !rect_overlap( first.m_extent, second ) )
		return result;

	t_clip_list::t_const_iterator rect_end  = first.m_rects.end();
	t_clip_list::t_const_iterator rect_iter = first.m_rects.begin();

	for ( ; rect_iter != rect_end; ++rect_iter )
	{
		if ( rect_overlap( *rect_iter, second ) == true)
		{
			first.m_global_free_rect_list->push_back_use_free_list ( result.m_rects, intersection( *rect_iter, second ) );
		}
	}

	result.update_extent();

	return result;
}

// ---------------------------------------------------------------
// Compute the intersection of a clip list and a rectangle : using an exising clip_lists cached
// rects.
// ---------------------------------------------------------------
 void		intersection_cached( t_clip_list & first, t_clip_list & second, t_screen_rect const & third )
{	
	if ((&first) == (&second))
		return;

	second.clear();

	if (rect_contains(third,first.m_extent))
	{
		std::list<t_screen_rect>::const_iterator rect_iter;
		
		for ( rect_iter = first.m_rects.begin(); rect_iter != first.m_rects.end(); ++rect_iter )
		{
			first.m_global_free_rect_list->push_back_use_free_list ( second.m_rects, *rect_iter );
		}

		return;
	}

	if ( !rect_overlap( first.m_extent, third ) )
		return;

	t_clip_list::t_const_iterator rect_end  = first.m_rects.end();
	t_clip_list::t_const_iterator rect_iter = first.m_rects.begin();
	for ( ; rect_iter != rect_end; ++rect_iter )
	{
		if ( rect_overlap( *rect_iter, third ) )
		{
			t_screen_rect rect = intersection( *rect_iter, third );
			
			first.m_global_free_rect_list->push_back_use_free_list ( second.m_rects, rect );
		}
	}

	second.update_extent();

	return;
}

